package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class QuickSort {

  public static void main(String[] args) {
    // int[] arr = {-9,78,0,23,-567,70, -1,900, 4561};

    // 测试快排的执行速度
    // 创建要给80000个的随机的数组
    int[] arr = new int[8000000];
    for (int i = 0; i < 8000000; i++) {
      arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
    }

    System.out.println("排序前");
    Date data1 = new Date();
    SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String date1Str = simpleDateFormat.format(data1);
    System.out.println("排序前的时间是=" + date1Str);

    quickSort(arr, 0, arr.length - 1);

    Date data2 = new Date();
    String date2Str = simpleDateFormat.format(data2);
    System.out.println("排序前的时间是=" + date2Str);
    // System.out.println("arr=" + Arrays.toString(arr));
  }

  /*
  快速排序，整体来看是这样： 首先令组内一个元素为基准pivot,所有比pivot小的站左边，大的站右边(从小到大排序)
  此时pivot的位置就是最终排序中的位置！！！，然后依次对左右两部分重复上述操作

  因为需要对各个部分进行排序，所以可以用左边界下标left和右边界下标right来隔开操作
  其实代码难实现的是怎么将小的放pivot左边，大人放pivot右边
  (其实简单的方法就是：先将pivot放第一个,然后遍历余下元素，大的不动，小的插入到第一个位置（原后移）)
   */
  public static void quickSort(int[] arr, int left, int right) {
    int l = left;
    int r = right;
    int pivot = arr[(left + right) / 2]; // pivot 取中轴值
    int temp = 0;
    // while循环的目的是让比pivot 值小放到左边，比pivot 值大放到右边
    while (l < r) { // 其实 l,r是用来实现上述难点的辅助指针
      // 在pivot的左边一直找,找到大于或等于pivot值,才退出
      while (arr[l] < pivot) {
        l += 1;
      } // 此时 [l] >= pivot
      // 在pivot的右边一直找,找到小于等于pivot值,才退出
      while (arr[r] > pivot) {
        r -= 1;
      } // 此时 [l] <= pivot
      // 如果l >= r说明已经分组好了
      if (l >= r) {
        break;
      }

      // 交换
      temp = arr[l];
      arr[l] = arr[r];
      arr[r] = temp;

      // 如果交换完后，发现这个arr[l] == pivot值 相等 r--(arr[l]本就是arr[r]上的元素,r可以前移了）
      if (arr[l] == pivot) {
        r -= 1;
      }
      // 如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
      if (arr[r] == pivot) {
        l += 1;
      }
    }

    // 如果 l == r, 必须l++, r--, 否则为出现栈溢出，只有这个情况 arr[l] = arr[r] = pivot
    if (l == r) {
      l += 1;
      r -= 1;
    }
    // 向左递归
    if (left < r) {
      quickSort(arr, left, r);
    }
    // 向右递归
    if (right > l) {
      quickSort(arr, l, right);
    }
  }
}
